package basis.netease.easy.废弃;

import java.util.LinkedList;
import java.util.Scanner;

/**
 * 7-10 判断二叉树是不是搜索树
 * 给定一个二叉树根节点，请你判断这棵树是不是二叉搜索树.
 * 输入格式:
 * 二叉搜索树满足每个节点的左子树上的所有节点均小于当前节点且右子树上的所有节点均大于当前节点。
 * 树上的节点数满足 1 <= n <= 10000, 每个节点的值满足 −2的31次方 <= val <= 2的31次方−1
 * 输出格式:
 * true or false
 * 输入样例:
 * 在这里给出一组输入（空节点用null-小写表示），例如：
 * 20,null,40,34,70,21,null,55,78
 * 输出样例:
 * 在这里给出相应的输出。例如：
 * true
 */
public class Main_10 {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        TreeNode root = buildTree(sc.nextLine().split(","));
        System.out.println(isValidBST(root));
    }

    public static boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private static boolean isValidBST(TreeNode node, long lower, long upper) {
        if (node == null) {
            return true;
        }
        int val = node.val;
        if (val <= lower || val >= upper) {
            return false;
        }
        return isValidBST(node.right, val, upper) && isValidBST(node.left, lower, val);
    }

    private static TreeNode buildTree(String[] values) {
        if (values[0].equals("null")) {
            return null;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        TreeNode root = new TreeNode(Integer.parseInt(values[0]));
        queue.offer(root);
        int i = 1;
        while (!queue.isEmpty() && i < values.length) {
            TreeNode current = queue.poll();
            if (!values[i].equals("null")) {
                current.left = new TreeNode(Integer.parseInt(values[i]));
                queue.offer(current.left);
            }
            i++;
            if (i < values.length && !values[i].equals("null")) {
                current.right = new TreeNode(Integer.parseInt(values[i]));
                queue.offer(current.right);
            }
            i++;
        }
        return root;
    }

}